#ifndef _MY_QUEUE_H_
#define _MY_QUEUE_H_

#include <atomic>
#include <memory>

using namespace std;

template<typename T>
class my_queue {
	public:
		void push(const T& data);
		unique_ptr<T> pop();
		
	private:
		struct node;
		
		struct countedNodePtr {
			int externalCount;
			node* ptr;
		};
		
		struct nodeCounter {
			unsigned int externalCounters : 2;
			unsigned int internalCount : 30;
		};
		
		struct node {
			atomic<T*> data;
			atomic<nodeCounter> count;
			atomic<countedNodePtr> next;
			
			void releaseRef() {
				nodeCounter oldCount = count.load();
				nodeCounter newCount;
				do {
					newCount = oldCount;
					--newCount.internalCount;
				} while (!count.compare_exchange_strong(oldCount, newCount));
				if (!newCount.externalCounters && !newCount.internalCount) {
					delete this;
				}
			}
		};
		
		atomic<countedNodePtr> head;
		atomic<countedNodePtr> tail;
		
		static void increaseExternalCount(atomic<countedNodePtr>& counter, countedNodePtr& oldCounter);
		static void freeExternalCounter(countedNodePtr& oldCounter);
		void setNewTail(countedNodePtr& oldTail, const countedNodePtr& newTail);
};

#include "my_queue.tcc"

#endif
